package com.notion.algorithms.datastructures.graph.algo;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

import com.notion.algorithms.datastructures.graph.Edge;
import com.notion.algorithms.datastructures.graph.Graph;
import com.notion.algorithms.datastructures.graph.Vertex;

public class GraphOperations {
	Set<Edge> mstEdges = new HashSet<Edge>();
	TreeMap<Edge,Vertex> crossingEdgeList = new TreeMap<Edge,Vertex>();
	public Set<Edge> getMinimumSpanningTree(Graph g){
		Vertex[] vertices = g.getVertices();
		Graph mst = new Graph(vertices.length);
		for(Edge e:vertices[0].getEdgeList()){
			crossingEdgeList.put(e, e.getOtherVertex(vertices[0]));
		}
		//RECURSIVELY CONSUME MIN COST EDGES IN MST SET 
		consumeEdgesInMST();
		//crossingEdgeList.addAll(vertices[0].getEdgeList());
		return mstEdges;
	}
	
	public void consumeEdgesInMST(){
		//END RECURSION
		if(crossingEdgeList.size()==0)
			return;
		Entry<Edge, Vertex> minCostEdge = findCrossingEdgeWithMinCost(crossingEdgeList);
		//crossingEdgeList.remove(minCostEdge.getKey());
		Vertex otherVertex = minCostEdge.getValue();
		Vertex remValue;
		for(Edge e:otherVertex.getEdgeList()){
			//NEWLY CONSUMED VERTEX.REMOVE OLDER CROSSING EDGES WHICH HAD THIS VERTEX AS UNCONSUMED
			//ALSO ADD EDGES ORIGINATING FROM THIS VERTEX WHICH WERE NOT PART OF CROSSING EDGES EARLIER
			//BUT ARE NOW, AS THIS EDGE IS CONSUMED
			remValue = crossingEdgeList.remove(e);
			if(null==remValue)
				//DIDN'T FIND THIS EDGE IN CROSSING EDGES, SO ADD NOW
				crossingEdgeList.put(e, e.getOtherVertex(otherVertex));
		}
		mstEdges.add(minCostEdge.getKey());
		consumeEdgesInMST();
	}
	private Entry<Edge, Vertex> findCrossingEdgeWithMinCost(TreeMap<Edge, Vertex> crossingEdgeList2){
		return crossingEdgeList2.firstEntry();
	}	

}
